package dynamicProgramming

// 动态规划解决0-1背包问题
// 对于一组不同重量，不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制下，求背包中物品总重的最大值
// items表示物品质量
// n 表示物品个数
// w 表示背包总承重

func Knapsack(weights []int, n, w int) (int, []int) {

	var states = make([][]bool, n)
	for k := 0; k < len(states); k++ {
		states[k] = make([]bool, w+1)
	}
	// 第一行的数据要特殊处理，可以利用哨兵优化
	states[0][0] = true
	if weights[0] <= w {
		states[0][weights[0]] = true
	}

	// 动态规划状态转移
	for i := 1; i < n; i++ {
		// 不把第i个物品放入背包
		// 那么该行的物品总量决策和上一个物品保持一致
		for j := 0; j <= w; j++ {
			if states[i-1][j] {
				states[i][j] = true
			}
		}
		// 把第i个物品放入背包
		// 当前物品决策 == 上一个物品决策+当前物品重量
		for j := 0; j <= w-weights[i]; j++ {
			if states[i-1][j] {
				states[i][j+weights[i]] = true
			}
		}
	}

	items := make([]int, n)
	maxW := 0

	for j := w; j >= 0; j-- {
		if states[n-1][j] {
			maxW = j
			break
		}
	}

	// 输出在最优解情况下都选择了哪些物品

	currentW := maxW
	for i := n - 1; i >= 1; i-- {
		if currentW-weights[i] >= 0 && states[i-1][currentW-weights[i]] {
			items[i] = 1
			currentW -= weights[i]
		}
	}

	if currentW == weights[0] {
		items[0] = 1
	}

	return maxW, items
}

// 优化版本
func Knapsack2(weights []int, n, w int) (int, []int) {
	var states = make([]bool, w+1)

	// 处理第一个物品
	states[0] = true
	if weights[0] <= w {
		// 只有第0个物品重量小于背包承重才能放入
		states[weights[0]] = true
	}

	for i := 1; i < n; i++ {
		// 当前物品不放入背包
		// 由于不放入背包后的状态集合与上一阶段完全一样，所以忽略

		// 把当前物品放入背包
		// j 必须从后往前计算，否则会出现for循环重复计算问题
		// 0 1 2 3 4 5  状态表索引
		// * * - * - -  上一个阶段状态表
		// 假设当前物品重量为2
		// * * * * * *  如果从小到大推导会重复计算
		// * * - * - *  从后大到下计算
		for j := w - weights[i]; j >= 0; j-- {
			if states[j] {
				states[j+weights[i]] = true
			}
		}
	}

	// 寻找状态表中重量接近w的下标
	maxW := 0
	for j := w; j >= 0; j-- {
		if states[j] {
			maxW = j
			break
		}
	}

	// 最优解情况下找一种物品选择方案
	items := make([]int, n)
	currentW := maxW
	for i := n - 1; i >= 1; i-- {
		if currentW-weights[i] >= 0 && states[currentW-weights[i]] {
			items[i] = 1
			currentW -= weights[i]
		}
	}
	if currentW == weights[0] {
		items[0] = 1
	}

	return maxW, items
}
